// #include <stdio.h>
// #include <stdlib.h>
// #include "windows.h"
//
// // 定义二叉树节点
// typedef struct ThreadNode {
//     int data;
//     struct ThreadNode *left, *right;
//     int ltag, rtag; // 线索标志: 0=子树指针, 1=前驱或后继线索
// } ThreadNode;
//
// ThreadNode* pre = NULL; // 全局变量，存储前驱节点
//
// // 创建新节点
// ThreadNode* CreateNode(int data) {
//     ThreadNode* node = (ThreadNode*)malloc(sizeof(ThreadNode));
//     node->data = data;
//     node->left = node->right = NULL;
//     node->ltag = node->rtag = 0;
//     return node;
// }
//
// // **中序遍历线索化**
// void InThread(ThreadNode* root) {
//     if (root == NULL) return;
//
//     InThread(root->left); // 递归左子树
//
//     // 处理当前节点的前驱线索
//     if (root->left == NULL) {
//         root->left = pre;
//         root->ltag = 1;
//     }
//
//     // 处理前驱节点的后继线索
//     if (pre != NULL && pre->right == NULL) {
//         pre->right = root;
//         pre->rtag = 1;
//     }
//
//     pre = root; // 更新前驱
//
//     InThread(root->right); // 递归右子树
// }
//
// // **初始化线索二叉树**
// void CreateInThread(ThreadNode* root) {
//     pre = NULL;
//     if (root != NULL) {
//         InThread(root);
//         if (pre != NULL) {
//             pre->right = NULL;
//             pre->rtag = 1; // 处理最后一个节点的后继线索
//         }
//     }
// }
//
// // **递归中序遍历**
// void RecursiveInOrder(ThreadNode* root) {
//     if (root == NULL) return;
//     if (root->ltag == 0) RecursiveInOrder(root->left); // 递归左子树
//     printf("%d ", root->data); // 访问根节点
//     if (root->rtag == 0) RecursiveInOrder(root->right); // 递归右子树
// }
//
// // **找到中序遍历的第一个节点（最左节点）**
// ThreadNode* FirstNode(ThreadNode* node) {
//     while (node != NULL && node->ltag == 0)
//         node = node->left;
//     return node;
// }
//
// // **找当前节点的后继节点**
// ThreadNode* NextNode(ThreadNode* node) {
//     if (node->rtag == 1) // 直接返回线索指向的后继
//         return node->right;
//     else
//         return FirstNode(node->right); // 找右子树中的最左节点
// }
//
// // **中序遍历（非递归，利用线索）**
// void InOrder(ThreadNode* root) {
//     for (ThreadNode* node = FirstNode(root); node != NULL; node = NextNode(node)) {
//         printf("%d ", node->data);
//     }
// }
//
// // **测试代码**
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     // 构造普通二叉树
//     ThreadNode* root = CreateNode(1);
//     root->left = CreateNode(2);
//     root->right = CreateNode(3);
//     root->left->left = CreateNode(4);
//     root->left->right = CreateNode(5);
//     root->right->left = CreateNode(6);
//     root->right->right = CreateNode(7);
//
//     // 线索化
//     CreateInThread(root);
//
//     // 递归中序遍历
//     printf("递归中序遍历: ");
//     RecursiveInOrder(root);
//     printf("\n");
//
//     // 线索化后的非递归遍历
//     printf("线索二叉树中序遍历: ");
//     InOrder(root);
//     printf("\n");
//
//     return 0;
// }
